#include <iostream>
#include <string.h>
#include "Heap.h"
using namespace std;
template<class T>
struct  HuffmanNode
{
	HuffmanNode<T>*  _parent;
	HuffmanNode<T>*  _left;
	HuffmanNode<T>*  _right;
	T  _weight;
	HuffmanNode(const T& x)
		:_parent(NULL)
		, _left(NULL)
		, _right(NULL)
		, _weight(x)
	{
	}
};
template <class T>
class  Huffman
{
	typedef  HuffmanNode<T>   Node;
public:
	Huffman()
		:_root(NULL)
	{}
	Huffman(T* a,size_t size,const T& invalid)
	{
		assert(a);
		struct  Less
		{
			bool  operator()(const Node* left, const Node* right)
			{
				return left->_weight < right->_weight;
			}
		};
		Heap<Node*, Less>  MinHeap;
		for (size_t i = 0; i < size; i++)
		{
			if (a[i] != invalid)
			{
				MinHeap.Push(new Node(a[i]));
			}
		}
			while (MinHeap.Size()>1)
			{
				Node* L = MinHeap.Top();
				MinHeap.Pop();
				Node* R = MinHeap.Top();
				MinHeap.Pop();

				Node* root = new Node(L->_weight + R->_weight);//构建父节点
				root->_left = L;
				root->_right = R;
				L->_parent = root;
				R->_parent = root;

				MinHeap.Push(root);//放入堆中重新调整
			}
			_root = MinHeap.Top();
	}
	Node* GetNode()
	{
		return _root;
	}
private:
	Node* _root;
};
